COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00011 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a50.tex[106,phy] \today\hfill}

\bigskip

Is 1729 an interesting number?  Yes, according to Ramanujan (``Rom-uh-NOO-jun''):
it is the smallest number that you can get by adding two perfect cubes in two
different ways.
$$\eqalign{10↑3  + 9↑3  &= 1000 + 729 = 1729\cr
	12↑3  + 1↑3  &= 1728 +   1 = 1729\cr}$$
We will develop an algorithm to find, in increasing order, any other such
``interesting'' numbers up to a million.

\smallskip
{\bf Method 1:} let  $N$  be a candidate for ``interesting.''  Iterate  $N$  
from~1 to~1000000.  Within this iteration, 
iterate  $A$, $B$, $C$, $D$  from~1 to~100, and print
the variables if $A↑3  + B↑3  = C↑3  + D↑3  = N$, and $A≠C$, $A≠D$.  
Unfortunately, the number of times we execute the inner iteration is  
$10↑6\times (100)↑4  = 10↑{14}$; at $10↑5$  executions per second, 
it will take 31.7 years.

\smallskip
{\bf Method 2:} just iterate $A$, $B$, $C$, $D$ from~1 to~100, 
printing if $A↑3 + B↑3 = C↑3 + D↑3$ and $A≠C$, $A≠D$.  
Now the program only needs 17~minutes for its $10↑8$ iterations, but
the numbers don't come out in increasing order.  Besides, we can do it much faster
by other algorithms.

\smallskip
{\bf Method 3:} Iterate $A$ and $B$ from 1 to~100, 
entering the value of $A↑3 + B↑3$ into
a table, and printing it if the value is already there.  The program only needs 
$10↑6$~operations, but still gives the results in the wrong order, 
and needs a huge table, larger than many computer memories.

\smallskip
{\bf Method 4:} We imagine the numbers that are the sums of two cubes 
arranged in a hundred lists; the seventeenth list would contain  
$17↑3 + 1$, $17↑3 + 8$, etc., through $17↑3 + 17↑3$.  
(Naturally, $17↑3 + 18↑3$ appears 
on the eighteenth list, so we don't need it on the seventeenth).  We will move
simultaneously through all the lists, always looking at only one number from
each list.  If a number is smaller than all the others, we replace it by the
next one on its list.  We keep the current numbers in a sorted table, so the
first entry is always the smallest.  If the first entry is equal to the second,
we have found an interesting number.

Let's watch the algorithm in action for a moment.  It has just passed the
number~1000.  The first seven lists are already exhausted.  No number
from the eleventh list has been reached yet, so there is no use looking at
the twelfth or later lists.  The sorted table looks like this:
$$\vcenter{\halign{\lft{#}$\;$&\rt{#}\quad&${#}$\hfill\cr
	List&10:&10↑3 + 1↑3 = 1001\cr
	List&8:&8↑3 + 8↑3 = 1024\cr
	List&9:&9↑3 + 7↑3 = 1072\cr
	List&11:&11↑3 + 0↑3 = 1331\cr}}$$
The algorithm finds that the two entries at the top of the table are different,
so it prints nothing.  It changes the top entry, first to
$10↑3 + 2↑3 = 1008$, then to $10↑3 + 3↑3 = 1027$, 
moving the entry down in the table:
$$\vcenter{\halign{\lft{#}$\;$&\rt{#}\quad&${#}$\hfill\cr
	List&8:&8↑3 + 8↑3 = 1024\cr
	List&10:&10↑3 + 3↑3 = 1027\cr
	List&9:&9↑3 + 7↑3 = 1072\cr
	List&11:&11↑3 + 0↑3 = 1331\cr}}$$
Now the entry from list 8 is the last of its list, so it is deleted.  A~little
later, the table is
$$\vcenter{\halign{\lft{#}$\;$&\rt{#}\quad&${#}$\hfill\cr
	List&11:&11↑3 + 0↑3 = 1331\cr
	List&10:&10↑3 + 7↑3 = 1343\cr
	List&9:&9↑3 + 9↑3 = 1458\cr}}$$
Having started to use list 11 as indicated by the $0↑3$, 
it is time to start looking
for numbers from List~12, so we add to the table the first number from List~12,
making the table:
$$\vcenter{\halign{\lft{#}$\;$&\rt{#}\quad&${#}$\hfill\cr
	List&11:&11↑3 + 1↑3 = 1332\cr
	List&10:&10↑3 + 7↑3 = 1343\cr
	List&9:&9↑3 + 9↑3 = 1458\cr
	List&12:&12↑3 + 0↑3 = 1728\cr}}$$
The number of steps of the algorithm is no more than 500 000; most of the work
comes in inserting each of the 5000 list entries into a table that never has
more than 100~entries.  In a computer program, we would work only with the
numbers from the tables; at the last stage shown above, we would have:
$$\vcenter{\halign{\ctr{#}\qquad&\ctr{#}\quad&\ctr{#}\quad&\ctr{#}\cr
	Subscript&Array&Array&Array\cr
	 $A$&$B$&$C$\cr
\noalign{\smallskip}
	    1&11&1&1332\cr
	    2&10&7&1343\cr
	    3&\phantom{0}9&9&1458\cr
	    4&12&0&1728\cr}}$$
\line{Variable\hfill}
\line{${\tt TABLESIZE}=4$\hfill}


Try programming the algorithm.  You will probably need subprograms to insert a
new entry in the table, to delete an entry, and to move the top entry down to
its correct location when it is not the smallest.

The contrast among the methods becomes far greater if you try it for numbers up
to a billion.  Method~1 then needs $10↑{16}$ seconds, or 317 million years.  
Methods~2
and~3 need a substantial fraction of a year.  Method~4 needs about ten~seconds.
Methods using a more advanced table arrangement, called a ``heap,'' can gain
another factor of ten or so.







\bigskip
\parindent0pt
\copyright 1984 Robert W. Floyd

First draft March  28, 1984

\bye